/*
 * Copyright (c) 2022.版权所有高金磊
 */

package 领扣算法.AA中等题.查找给定哈希值的子串;

public class Main {
    public static void main(String arg[]){//main--来自高金磊

        new Main().subStrHash("xmmhdakfursinye",96,                45,                15,                21);
    }

    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] data=s.toCharArray();
        long cache=0;
        int sta=0;
        for (int i = 0; i < k; i++) {
            cache+=(data[i]-'a'+1)*Math.pow(power, i);
            cache%=modulo;
        }
        long max=(int) Math.pow(power, k-1);
        while (cache%modulo!=hashValue){
            sta++;
            cache-=(data[sta-1]-'a'+1);
            cache/=power;
            cache+=(data[sta+k-1]-'a'+1)*max;
            cache%=modulo;
        }
        StringBuilder stringBuilder=new StringBuilder();
        for (int i = sta; i < sta + k; i++) {
            stringBuilder.append(data[i]);
        }
        return stringBuilder.toString();
    }
}
